The present invention relates to a circuit arrangement for noncyclic data permutations between the memory cells of a dyanmic memory having a permutation network for transferring the contents of a predetermined memory cell to the read-write cell of the memory and an access control system for producing a permutation sequence.
In computer systems, disc and drum memories are used predominantly to store large quantities of data. In these memories the data are recorded on a magnetic medium which performs a continuous rotating movement at constant speed with respect to a fixed write-read or input-output head. A drawback of this cyclic data movement relative to the reading head is that the access time for any desired datum depends on its position with respect to the reading head at the moment it is being addressed so that as a statistical average one-half revolution of the record carrier is required before the desired datum can be read out or written in. The time required for this lies in the range of milliseconds so that direct access by the central processing unit, which operates by about three to four orders of magnitude faster, is economically unjustified. Therefore, these dynamic memories are used as background memories from which contiguous data blocks are initially transferred via independently operating channel systems to the main memory before access is possible by the central processor. In this way, the central processing unit can bridge the access time gap resulting from calling a data block from the background memory with other activity. This process, however, is connected with substantial administrative efforts, for example, for releasing a memory region, providing a channel program and treating interrupts. Furthermore, the transfer of a contiguous data block is often not necessary at all if, for example, only individual data need to be inspected. For these reasons it is advisable to provide the central processing unit with rapid direct access to individual data as well as to contiguous data blocks which are stored in background memories of very large capacity.
Background memories can be realized only through techniques which are distinguished by low costs per bit and an extremely high data packing density. In this respect, charge transfer devices seem to be particularly well suited instead of drum memories and magnetic domain devices instead of disc memories. These techniques, in contradistinction to disc and drum memories, require continuous movement of data relative to the memory medium itself as well as relative to the write-read head which is attached to the memory medium. Due to the movement relative to the memory medium it becomes possible to implement switching functions so that data movement need not be limited to cyclic movement. Rather the contents of a memory cell can be selectively transferred to one of two or more successor cells while the cell itself at the same time takes over the contents of one of two or more precursor cells. In this way several paths or more exactly one very short path is available on which the contents of an arbitrarily selected cell can be transported to the read-write cell.
A permutation shuffle or transformation network is known (IEEE Transactions on Computers, Volume C-2, No. 4(1972), p. 359-366) which is based on a tree-like connecting structure in which every memory cell has exactly two successor cells and two precursor cells. All connections within the network are associated to two permutations of which the connections of one permutation are activated simultaneously. The two permutations are arranged so that in a memory having 2.sup.k cells the contents of each cell can be brought to the read-write cell, i.e., the access port or input-output port cell, of the memory in at most k steps.
In another known permutation network (IEEE Transactions on Computers Vol. C-23, No. 3 (1974) pages 272-276) the connections between the cells are arranged so that with a total capacity of 2.sup.k -1 cells and likewise two permutations, the contents of a cell can be transported to the read-write cell in the order of magnitude of k steps; however the contents of all sequentially following cells can be transported to the read-write cell in one further step each.
A decisive drawback of both networks is that connections must be established between non-adjacent memory cells and with the appropriate memory capacities such connections require a complex, nonplanar connecting network with a substantial number of line crossovers which calls for a considerable proportion of the area available on the memory chip. These networks are entirely unsuitable for magnetic domain devices since here it is not possible to transport data over greater distances in one permutation clock time.